package blueBridge;

import java.util.Scanner;

/*

3 2

16



                          选(0, 0)                              不选(0, 0)
                       /            \                          /         \
               选(0, 1)              不选(0, 1)         选(0, 1)           不选(0, 1)
               /     \               /      \           /     \             /      \
         选(0, 2)   不选(0, 2)  选(0, 2)  不选(0, 2)  选(0, 2)   不选(0, 2)  选(0, 2)  不选(0, 2)
          ...


dp[i][st][k]含义：第0~i行总共放了k个国王，第i行的状态为st时的方案数
这个dp数组的细节
100
000   此时的状态为[1][000][1]
000

而
010
000   此时的状态也是[1][000][1]
000

001
000   此时的状态也是[1][000][1]
000
但是第二行的状态是确定的，所以第一行的状态不影响第三行的数据
因此这三个状态视为同一状态

这个状态存储方式很妙，但是我的存储时机不对
必须换一个搜索方式

        [0][100][1]                     [0][010][1]     [0][001][1]     [0][000][0]
        /       \       \           \
[1][100][2] [1][010][2] [1][001][2] [1][000][1]
    F           F           T      /    |       \           \
                        [2][100][2] [2][010][2] [2][001][2] [2][000][1]
                             T          T           T           F

然后debug又卡手了，问题出在变量开得太小了，得养成习惯，开变量之前先算一下数据会不会溢出，debug的时候
自己测试的所有数据都没问题，但提交就是过不了，你得想到这个问题。

 */

public class Main887_Three {
    int n;
    int k;
    int okSize;
    int[] okLine;
    int[] addStep;
    int[] board;
    long dp[][][];
    
    

    private Main887_Three(int n, int k) {
        super();
        this.n = n;
        this.k = k;
        okLine = new int[(1 << n)];
        addStep = new int[okLine.length];
        // 先列出行内可行的情况，避免后面重复枚举
        for (int i = 0; i < okLine.length; i++) {
            if ((i & (i >> 1)) == 0) {
                int temp = i;
                while (temp > 0) {
                    temp &= (temp - 1);
                    addStep[okSize]++;
                }
                okLine[okSize++] = i;
            }
        }
        /*
        for (int i = 0; i < okSize; i++) {
            System.out.println(Integer.toBinaryString(okLine[i]) + ", " + addStep[i]);
        }
        */
        dp = new long[n][okLine.length][k];
        // 初始化dp数组
        for (int row = 0; row < n; row++) {
            for (int status = 0; status < (1 << n); status++) {
                for (int step = 0; step < k; step++) {
                    dp[row][status][step] = -1;
                }
            }
        }
        board = new int[n];
    }
    private long getCount() {
        long count = 0;
        for (int i = 0; i < okSize; i++) {
            board[0] = okLine[i];
            count += dfs(0, board[0], addStep[i]);
        }
        return count;
    }
    
    private long dfs(int row, int status, int step) {
        if (step == k) {
            for (int i = 0; i < n; i++) {
                System.out.println(Integer.toBinaryString(board[i]));
            }
            System.out.println();
            return 1;
        }
        if (step > k || row >= n-1) {
            return 0;
        }
        if (dp[row][status][step] != -1) {
            // System.out.println(dp[row][status][step] + " => " + row + ", " + Integer.toBinaryString(status) + ", " + step);
            return dp[row][status][step];
        }
        long count = 0;
        for (int i = 0; i < okSize; i++) {
            int temp = board[row+1];
            board[row+1] = okLine[i];
            // 如果与上一行不冲突，继续深搜
            if (((board[row+1] & board[row]) == 0) && ((board[row+1] & (board[row]) << 1) == 0) && ((board[row+1] & (board[row] >> 1)) == 0)) {
                count += dfs(row+1, board[row+1], step + addStep[i]);
            }
            board[row+1] = temp;
        }
        dp[row][status][step] = count;
        // System.out.println(count + " => " + row + ", " + Integer.toBinaryString(status) + ", " + step);
        return count;
    }
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int k = scan.nextInt();
        Main887_Three m = new Main887_Three(n, k);
        System.out.println(m.getCount());

    }








    





    

}
